package exp2.test2;

import java.util.Objects;

/**
 * Created by 春旺 on 2017/10/24.
 */
public class ComeTree <T>{
    public static class Tree<T>{
        public T value;
        public Tree left;
        public Tree right;
        public Tree(T value) {
            this.value=value;
        }
    }
    public  Tree buildTree(Object[]pre,Object[]mid){
        T value= (T) pre[0];
        int length=pre.length;
        Tree root=new Tree(value);
        root.left=root.right=null;
        if (pre.length==1) {
            return root;
        }
        int ai=0;
        while(mid[ai]!=value)
            ai++;
        if (ai>0) {
            Object[]leftSubPreOrder=new Object[ai];
            for(int i=0;i<leftSubPreOrder.length;i++){
                leftSubPreOrder[i]=pre[i+1];
            }
            Object[]leftMid=new Object[ai];
            for(int i=0;i<leftMid.length;i++){
                leftMid[i]=mid[i];
            }
            root.left=buildTree(leftSubPreOrder, leftMid);
        }

        if(length-ai-1>0){
            Object[]rightSubMidOrder=new Object[length-ai-1];
            for(int i=0;i<rightSubMidOrder.length;i++){
                rightSubMidOrder[i]=mid[i+ai+1];
            }
            Object[]rightSubPreOrder=new Object[length-ai-1];

            for(int i=0;i<rightSubPreOrder.length;i++){
                rightSubPreOrder[i]=pre[i+ai+1];
            }
            root.right=buildTree(rightSubPreOrder, rightSubMidOrder);
        }
        return root;
    }
    public static void behindOrder(Tree root){
        if (root==null) {
            return;
        }
        if (root.left!=null) {
            behindOrder(root.left);
        }
        if (root.right!=null) {
            behindOrder(root.right);
        }
        System.out.print(root.value+" ");

    }
    public  void getBehindOrder(Object[]pre,Object[]mid){
        if (pre==null||mid==null||pre.length!=mid.length) {
            return;
        }
        Tree root=this.buildTree(pre, mid);

        behindOrder(root);
    }

}
